﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MultiGed2.Topologie
{
 /// <summary>
 /// Stav hledani cesty mezi dopravnami.
 /// </summary>
 sealed class StavHledani
 {
  /// <summary>
  /// Prubeh hledani.
  /// </summary>
  public enum Prubeh {
   /// <summary>
   /// Hledani probiha.
   /// </summary>
   Hledani,
   /// <summary>
   /// Cesta nalezena.
   /// </summary>
   Nalezeno,
   /// <summary>
   /// Cesta nenalezena.
   /// </summary>
   Nenalezeno
  }

  /// <summary>
  /// Seznam dopraven, navstivenych pri hledani.
  /// </summary>
  public List<Dopravna> navstivene;
  /// <summary>
  /// Posledni navstivena dopravna.
  /// </summary>
  public Dopravna aktDopr;
  /// <summary>
  /// Aktualni smer prohledavani.
  /// </summary>
  public SmerJizdy aktSmer;
  /// <summary>
  /// Prubeh hledani.
  /// </summary>
  public Prubeh prubeh;

  /// <summary>
  /// Konstruktor noveho stavu hledani, musi byt volany na zacatku hledani.
  /// </summary>
  /// <param name="aktualni">Vychozi dopravna.</param>
  /// <param name="smer">Smer prohledavani.</param>
  public StavHledani(Dopravna aktualni, SmerJizdy smer)
  {
   navstivene = new List<Dopravna>();
   aktDopr = aktualni;
   aktSmer = smer;
   prubeh = Prubeh.Hledani;
  }

  /// <summary>
  /// Kopirovaci konstruktor (pro vetveni hledani).
  /// </summary>
  /// <param name="stav">Stav hledani, podle ktereho bude zkonstruovan novy stav.</param>
  public StavHledani(StavHledani stav)
  {
   navstivene = new List<Dopravna>(stav.navstivene);
   aktDopr = stav.aktDopr;
   aktSmer = stav.aktSmer;
   prubeh = Prubeh.Hledani;
  }
 }

 /// <summary>
 /// Staticka trida s vyhledavacimi funkcemi.
 /// </summary>
 public static class Hledani
 {
  /// <summary>
  /// Najde tratove koleje, vedouci z Dopravny v danem smeru.
  /// </summary>
  /// <param name="dopravna">Dopravna, ze ktere se hledaji koleje.</param>
  /// <param name="smer">Smer hledani.</param>
  /// <param name="kolejeOblasti">Seznam koleji k prohledavani.</param>
  /// <returns>Seznam tratovych koleji.</returns>
  static private List<TrKolej> KolejeZDopravnyVeSmeru(Dopravna dopravna, SmerJizdy smer,
   List<TrKolej> kolejeOblasti)
  {
   return kolejeOblasti.Where(kolej => kolej.dopravnaZ == dopravna && kolej.smerZ == smer).ToList();
  } // KolejeZDopravnyVeSmeru

  /// <summary>
  /// Najde trasy (jako seznam stavu hledani) mezi dvemi dopravnami
  /// v zadanem smeru.
  /// </summary>
  /// <param name="dopravnaZ">Vychozi dopravna.</param>
  /// <param name="dopravnaDo">Dopravna, do ktere se hleda trasa.</param>
  /// <param name="smer">Smer hledani.</param>
  /// <param name="kolejeOblasti">Seznam tratovych koleji.</param>
  /// <returns>Seznam uspesnych stavu hledani.</returns>
  static private List<StavHledani> NajdiTrasuBezUvrati(
   Dopravna dopravnaZ, Dopravna dopravnaDo,
   SmerJizdy smer, List<TrKolej> kolejeOblasti)
  {
   // inicializace hledani
   List<StavHledani> stavyHledani = new List<StavHledani>()
   {
    new StavHledani(dopravnaZ, smer)
   };

   bool konec = false;
   // nove stavy pro vetveni
   List<StavHledani> noveStavy = new List<StavHledani>();

   while (!konec)
   {
    noveStavy.Clear();

    // iterace "nadejnych" stavu hledani
    foreach (StavHledani stav in stavyHledani.Where(
     s => s.prubeh == StavHledani.Prubeh.Hledani))
    {
     // nalezeno
     if (stav.aktDopr == dopravnaDo)
     {
      stav.prubeh = StavHledani.Prubeh.Nalezeno;
      continue;
     }

     // pokracovat v hledani z posledni dopravny
     List<TrKolej> najiteKoleje = KolejeZDopravnyVeSmeru(
      stav.aktDopr, stav.aktSmer, kolejeOblasti);
     // nic nenalezeno
     if (najiteKoleje.Count == 0)
     {
      stav.prubeh = StavHledani.Prubeh.Nenalezeno;
      continue;
     }
     // nalezena aspon jedna kolej
     else
     {
      stav.navstivene.Add(stav.aktDopr);
      stav.aktDopr = najiteKoleje[0].dopravnaDo;
      stav.aktSmer = najiteKoleje[0].smerDo;
     }
     // vice nez jedna -> vetveni
     if (najiteKoleje.Count > 1)
     {
      foreach (TrKolej kolej in najiteKoleje.Skip(1))
      {
       StavHledani novy = new StavHledani(stav);
       novy.aktDopr = kolej.dopravnaDo;
       novy.aktSmer = kolej.smerDo;
       noveStavy.Add(novy);
      }
     }
    }

    // pridat vetveni
    foreach (StavHledani novy in noveStavy)
     stavyHledani.Add(novy);

    // je jeste co prohledavat?
    if (stavyHledani.Where(
     s => s.prubeh == StavHledani.Prubeh.Hledani).Count() == 0)
     konec = true;
   } // while !konec

   // najit nalezene trasy
   return stavyHledani.Where(
    s => s.prubeh == StavHledani.Prubeh.Nalezeno).ToList();
  } // NajdiTrasuBezUvrati

  /// <summary>
  /// Najde trasy (jako seznamy dopraven) mezi dvemi dopravnami
  /// v zadanem smeru.
  /// </summary>
  /// <param name="dopravnaZ">Vychozi dopravna.</param>
  /// <param name="dopravnaDo">Dopravna, do ktere se hleda trasa.</param>
  /// <param name="smer">Smer hledani.</param>
  /// <param name="kolejeOblasti">Seznam koleji k prohledavani.</param>
  /// <returns>Seznam tras (jako seznamu dopraven).</returns>
  static private List<List<Dopravna>> TrasaZDo(
   Dopravna dopravnaZ, Dopravna dopravnaDo,
   SmerJizdy smer, List<TrKolej> kolejeOblasti)
  {
   List<StavHledani> nalezene = NajdiTrasuBezUvrati(dopravnaZ, dopravnaDo, smer, kolejeOblasti);
   List<List<Dopravna>> vysledek = new List<List<Dopravna>>();
   foreach(StavHledani stav in nalezene)
   {
    List<Dopravna> novy = new List<Dopravna>(stav.navstivene);
    novy.Add(stav.aktDopr);
    vysledek.Add(novy);
   }
   return vysledek;
  } // TrasaZDo

  /// <summary>
  /// Najde trasy (jako seznamy dopraven) mezi dvemi dopravnami
  /// (bez zadani smeru).
  /// </summary>
  /// <param name="dopravnaZ">Vychozi dopravna.</param>
  /// <param name="dopravnaDo">Dopravna, do ktere se hleda trasa.</param>
  /// <param name="oblast">Oblast hledani.</param>
  /// <returns>Seznam tras (jako seznamu dopraven).</returns>
  static public List<List<Dopravna>> TrasaZDo(
   Dopravna dopravnaZ, Dopravna dopravnaDo, Oblast oblast)
  {
   List<List<Dopravna>> vysledek;
   vysledek = TrasaZDo(dopravnaZ, dopravnaDo, SmerJizdy.Sudy, oblast.koleje);
   vysledek.AddRange(TrasaZDo(dopravnaZ, dopravnaDo, SmerJizdy.Lichy, oblast.koleje));
   // formalizovat trasy
   return vysledek.Select(trasa => FormalizujTrasu(trasa, oblast)).ToList();
  }

  static public List<List<Dopravna>> TrasaZDo2(
   Dopravna dopravnaZ, Dopravna dopravnaPres, Dopravna dopravnaDo, Oblast oblast)
  {
   List<List<Dopravna>> vysledek = null, tmp1, tmp2;
   tmp1 = TrasaZDo(dopravnaZ, dopravnaPres, oblast);
   tmp2 = TrasaZDo(dopravnaPres, dopravnaDo, oblast);
   if (tmp1.Count > 0 && tmp2.Count > 0)
   {
    vysledek = new List<List<Dopravna>>();
    foreach (List<Dopravna> t1 in tmp1)
    {
     foreach (List<Dopravna> t2 in tmp2)
     {
      List<Dopravna> t = new List<Dopravna>(t1);
      t.AddRange(t2.Skip(1));
      vysledek.Add(t);
     }
    }
   }
   return vysledek;
  }

  /// <summary>
  /// Odstrani z trasy pomocne dopravny tak,
  /// aby zustala zachovana jen "hlavni" dopravna,
  /// pokud to je mozne.
  /// </summary>
  /// <param name="trasa"></param>
  /// <returns></returns>
  static private List<Dopravna> FormalizujTrasu(List<Dopravna> trasa, Oblast oblast)
  {
   List<Dopravna> vysledek = new List<Dopravna>();
   string pouziteKody = "";
   foreach (Dopravna dopravna in trasa)
   {
    char k = dopravna.kod;
    if (!pouziteKody.Contains(k))
    {
     Dopravna novaDop = dopravna;
     foreach(Dopravna dopTmp in oblast.dopravny.Where(
      dop => dop.kod == k))
      if (dopTmp.kategorie == KategorieDopravny.Zst)
      {
       novaDop = dopTmp;
       break;
      }
     vysledek.Add(novaDop);
     pouziteKody += k;
    }
   }
   return vysledek;
  }
 }
}
